package com.atguigu.pa;

import java.util.Arrays;

public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {8,10,2,5,14,4,12,1,6,9,15,3,7,13,11};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }


    private static void quickSort(int[] arr , int start ,int end){
        if(start>=end){
            return ;
        }
        //partition这个方法的作用有两个：
        //1.返回基准元素的索引位置，这样我们就能将大数组拆分成两个小数组
        //2.在partition方法内部找基准位置的时候，已经将基准元素挪过去了。因此这一次partition能够保证基准元素的位置是正确的
        int pivotIndex = partition(arr,start,end);
        quickSort(arr,start,pivotIndex-1);
        quickSort(arr,pivotIndex+1,end);
    }

    private static int partition(int[] arr , int start ,int end){
        //low用来记录浅颜色指针
        int low = start ;
        //high用来记录深蓝色指针
        int high = end ;

        //假设第一个位置的元素是基准元素
        int pivot = arr[start];

        while(low<high) {
            //首先从高位开始判断(因为基准元素选择的是第一个位置)
            while (low<high && arr[high] >= pivot) {
                high--;
            }
            arr[low] = arr[high];

            while (low<high && arr[low] < pivot) {
                low++;
            }
            arr[high] = arr[low];
        }
        arr[low]=pivot;
        return low;
    }
}
